//完全背包
#include <iostream>
using namespace std;
const int MAXN=30;
const int MAXM=200;

int n,m;
int w[MAXN+1],c[MAXN+1];
int maxc[MAXM+1];//maxc[v]容量为v取得的最大价值

int main(){
    cin>>m>>n;
    for(int i=1;i<=n;i++) cin>>w[i]>>c[i];

    for(int i=1;i<=n;i++)
        for(int v=w[i];v<=m;v++){
            maxc[v]=max(maxc[v],maxc[v-w[i]]+c[i]);
        }
    cout<<maxc[m];
}
